package com.linyaonan.leetcode.sword_to_offer._26;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 * 给定的树 B：
 *
 *    4 
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 示例 1：
 *
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 * 示例 2：
 *
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 * 限制：
 *
 * 0 <= 节点个数 <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 异常边界
        if (A == null || B == null) {
            return false;
        }
        // 首个可以与B进行匹配的假设是A本身
        TreeNode firstCom = A;
        while (firstCom != null) {
            // 找到真正数值匹配的节点头
            firstCom = bfs(A, B.val);
            // 递归进行匹配，直到A或者B结束
            boolean b = bfsEqual(firstCom, B);
            if (b) {
                return true;
            } else {
                // 不匹配后还需要继续向后查找与B相同的头节点
                if (firstCom != null) {
                    // 考虑到b的值是边界则进行特殊处理，否则直接+1，重新匹配后就会跳过
                    if (B.val < Integer.MAX_VALUE) {
                        firstCom.val = B.val + 1;
                    } else {
                        firstCom.val = Integer.MIN_VALUE;
                    }
                }
            }
        }

        return false;
    }

    public boolean bfsEqual(TreeNode A, TreeNode B) {
        if (B == null)
            return true;
        if (A == null)
            return false;
        if (A.val == B.val) {
            return bfsEqual(A.left, B.left) && bfsEqual(A.right, B.right);
        }
        return false;
    }

    /**
     * 找到首个与目标数值相同的指针
     * @param node
     * @param v
     * @return
     */
    public TreeNode bfs(TreeNode node, int v) {
        if (node == null)
            return null;
        if (node.val == v) {
            return node;
        } else {
            TreeNode l = bfs(node.left, v);
            if (l != null) {
                return l;
            }
            TreeNode r = bfs(node.right, v);
            return r;
        }
    }
}